/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-12-13
 * Time: 22:36
 */
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public ListNode sortList(ListNode head) {
        int length=getLength(head);//记录链表的长度
        ListNode newHead=new ListNode(0,head);//在原链表的基础上再多加一个哨兵位节点更方便
        for(int gap=1;gap<length;gap<<=1){
            //gap表示每组节点个数
            // 这里gap<length,因为gap每次*2,要确保gap>=(length+1)/2,所以gap<length
            ListNode prevTail=newHead;//prevTail要一直记录前面的尾节点,初始值要记录哨兵位
            ListNode cur=newHead.next;//这里记住每次进来cur都是真正的头节点,不能是head
            while(cur!=null){
                ListNode headLeft=cur;//左边的头节点
                //先找到右边那一组的头节点的前一个结点,将连接断开
                for(int step=1;step<gap&&cur.next!=null;step++){
                    cur=cur.next;
                }
                ListNode headRight=cur.next;//右边的头节点
                //与前面一组断开连接
                cur.next=null;
                cur=headRight;

                //右边的那一组与右边断开连接
                for(int step=1;step<gap&&cur!=null&&cur.next!=null;step++){
                    cur=cur.next;
                }
                //记录下一组的起始位置
                ListNode nextGroup=null;
                if(cur!=null){
                    nextGroup=cur.next;
                    cur.next=null;
                }
                //归并这两组
                ListNode merged=merge(headLeft,headRight);
                //与之前归并过的连接起来
                prevTail.next=merged;
                //prevTail要一直记录前面的尾节点
                while(prevTail.next!=null){
                    prevTail=prevTail.next;
                }
                //转移cur开始后面的归并
                cur=nextGroup;
            }
        }
        return newHead.next;
    }

    /**
     合并两个有序链表
     */
    public ListNode merge(ListNode headLeft,ListNode headRight){
        ListNode newHead=new ListNode(0);
        ListNode tail=newHead;
        ListNode temp1=headLeft;
        ListNode temp2=headRight;
        while(temp1!=null&&temp2!=null){
            if(temp1.val<temp2.val){
                tail.next=temp1;
                temp1=temp1.next;
            }else{
                tail.next=temp2;
                temp2=temp2.next;
            }
            tail=tail.next;
            tail.next=null;//这里有没有都行,因为tail最后一定指向最后一个节点,最后一个节点一定是空,因为前面已经断开了
        }
        if(temp1!=null){
            tail.next=temp1;
        }
        if(temp2!=null){
            tail.next=temp2;
        }
        return newHead.next;
    }


    public int getLength(ListNode head){
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
}
